
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Date;
import java.text.SimpleDateFormat;
import java.util.ArrayList;

public class SubSumHash {
	
	HashMap<String, Long> hashData = null;
	HashMap<Long, Long> hashMapLL = null; 
	
	ArrayList<ArrayList<Long>>simpleHash = null;
	int tableSize = 0;
	int []sumArray;
	int offset = 1000;
	
	public void ConstructHashTable(){
		PrintCurrentTime("start construct hash table <String, Long>");
		hashData = new HashMap<String, Long>();
		DataReader reader = new DataReader();
		if(!reader.SetFilename("C:\\tmp\\2sum.txt"))
		{
			System.out.println("failed to init file reader!");;
		}
		
		String str = null;
		while((str = reader.GetNextLine()) != null)
		{
			hashData.put(new String(str), new Long(str));
		}
		
		sumArray = new int[offset * 2 + 1];
	}
	
	public void ConstructHashTableL(){
		PrintCurrentTime("start construct hash table <Long, Long>");
		hashMapLL = new HashMap<Long, Long>();
		DataReader reader = new DataReader();
		if(!reader.SetFilename("C:\\tmp\\2sum.txt"))
		{
			System.out.println("failed to init file reader!");;
		}
		
		String str = null;
		while((str = reader.GetNextLine()) != null)
		{
			hashMapLL.put(new Long(str), new Long(str));
		}
		
		sumArray = new int[offset * 2 + 1];
	}
	
	
	public void ConstructSimpleHash()
	{
		PrintCurrentTime("start construct simple hash table");
		tableSize = 1<<21;
		simpleHash = new ArrayList<ArrayList<Long>>(tableSize);
		
		for(int i = 0; i < tableSize; i++){
			ArrayList<Long> al = new ArrayList<Long>(1);
			simpleHash.add(al);
		}
		
		DataReader reader = new DataReader();
		if(!reader.SetFilename("C:\\tmp\\2sum.txt"))
		{
			System.out.println("failed to init file reader!");;
		}
		
		String str = null;
		while((str = reader.GetNextLine()) != null)
		{
			long value = Long.parseLong(str);
			int index = (int)(value&0x1FFFFF);

			ArrayList<Long> al = simpleHash.get(index);
			al.add(new Long(value));
		}
		
		sumArray = new int[offset * 2 + 1];
	}
	
	
	public void PrintData()
	{
		/*Iterator<Map.Entry<String, Long>> itor = hashData.entrySet().iterator();
		
		while(itor.hasNext())
		{
			Map.Entry<String, Long> entry = itor.next();
			Long value = entry.getValue();
			if(value != null)
			System.out.println(value);
		}*/
		int sum = 0;
		for(int i = 0; i < sumArray.length; i++)
		{
			if(sumArray[i] != 0)
			{
				System.out.print(i - offset + "\t");
				sum++;
			}
		}
		
		System.out.print("\n");
		System.out.println("result is: " + sum);
	}
	
	
	public void PrintCurrentTime(String strPrefix){
		System.out.println(strPrefix);
		SimpleDateFormat sf = new SimpleDateFormat("HH:mm:ss.SSS");
		System.out.println(sf.format(new Date()));
	}
	
	
	public void Compute2Sum()
	{
		PrintCurrentTime("start hash search for 2sum");
		Iterator<Map.Entry<String, Long>> itor = hashData.entrySet().iterator();
		
		while(itor.hasNext())
		{
			Map.Entry<String, Long> entry = itor.next();
			Long value = entry.getValue();
			
			//0 ~ -10000, 10000 ~ 0, 10001 ~ 1
			for(int i = 0; i < offset * 2 + 1; i++){
				if(sumArray[i] == 0){
					long value2Search = (i - offset) - value.longValue();
					String key2Search = new Long(value2Search).toString();
					
					Long hashValue = hashData.get(key2Search);
					if(hashValue != null && value2Search == hashValue.longValue()
							&& !value.equals(hashValue))
					{
						sumArray[i] = 1;
					}
				}
			}
		}
		PrintCurrentTime("end of hash search for 2sum");
	}
	
	public void Compute2SumL()
	{
		PrintCurrentTime("start hash search for 2sum LL");
		Iterator<Map.Entry<Long, Long>> itor = hashMapLL.entrySet().iterator();
		
		while(itor.hasNext())
		{
			Map.Entry<Long, Long> entry = itor.next();
			Long value = entry.getValue();
			
			//0 ~ -10000, 10000 ~ 0, 10001 ~ 1
			for(int i = 0; i < offset * 2 + 1; i++){
				if(sumArray[i] == 0){
					long value2Search = (i - offset) - value.longValue();
					Long key2Search = new Long(value2Search);
					
					Long hashValue = hashMapLL.get(key2Search);
					if(hashValue != null && value2Search == hashValue.longValue()
							&& !value.equals(hashValue))
					{
						sumArray[i] = 1;
					}
				}
			}
		}
		PrintCurrentTime("end of hash search for 2sum LL");
	}
	
	public void Compute2SumBySimpleTable()
	{
		PrintCurrentTime("start hash search for 2sum simple hash");
		
		for(int i = 0; i < tableSize; i++)
		{
			ArrayList<Long> al = this.simpleHash.get(i);
			
			for(int j = 0; j < al.size(); j++)
			{				
				Long value = al.get(j);
				for(int k = 0; k < offset * 2 + 1; k++)
				{
					if(sumArray[k] == 0)
					{
						long value2Search = (k - offset) - value.longValue();
						
						int index = (int)(value2Search&0x1FFFFF);
						
						ArrayList<Long> searchAL = simpleHash.get(index);
						
						for(int l = 0; l < searchAL.size(); l++)
						{
							if(searchAL.get(l).longValue() == value2Search && !searchAL.get(l).equals(value))
							{
								sumArray[k] = 1;
							}
						}
					}
				}
			}
		}
		
		PrintCurrentTime("end of hash search for 2sum simple hash");
	}
	
	public void PrintPrime(){
		for(int i = 500000; i < 1500000; i++){
			int j = 0;
			for(j = 2; j*j <= i; j++)
			{
				if(i%j == 0)
					break;
			}
			
			if(j*j > i)
			{
				System.out.print(i + ",");
			}
		}
		
		System.out.println("print prime is over");
	}

}
